//
// Created by guanyicheng on 2022/5/13.
//

#include "../../common.h"

// 时间复杂度：O(nlogk)
// 空间复杂度：O(n)
class Solution {

    struct compare1 {

        bool operator()(const pair<int, int> &a, const pair<int, int> &b) const { return a.second > b.second; }
    };

public:
    vector<int> topKFrequent(vector<int> &nums, int k) {

        unordered_map<int, int> _map{};
        for (int &n: nums) {
            _map[n]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, compare1> priorityQueue{};
        for(auto &pair: _map) {
            priorityQueue.emplace(pair);
            if (priorityQueue.size() > k) {
                priorityQueue.pop();
            }
        }

        vector<int> res{};
        while (!priorityQueue.empty()) {
            res.emplace_back(priorityQueue.top().first);
            priorityQueue.pop();
        }
        return res;
    }
};

int main() {
    auto v1 = vector<int>{1, 1, 1, 2, 2, 3};
    cout << Solution().topKFrequent(v1, 3).size() << endl;
}